package Tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 *  题目 ：获取二叉树最底层最左边的节点值
 *  题目详述 ：
 *  给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
 *  假设二叉树中至少有一个节点。
 */
public class P45 {
    /**
     * 核心思想 ：
     * 由于其是与二叉树的层有关，即第一个想到的是二叉树广度优先遍历
     */
    public int findBottomLeftValue(TreeNode root) {
        // 方法一 ：使用current，next，来记录当前层数的节点数，下一层的节点数
        // 队列的初始化 ：由于二叉树至少有一个节点，所以queue队列中插入根节点
        /*
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        // 初始化
        int currentSum = 1;
        int nextSum = 0;
        int result = root.val;
        while(!queue.isEmpty()){
            TreeNode pollNode = queue.poll();
            currentSum--;
            if(pollNode.left != null){
                queue.offer(pollNode.left);
                nextSum++;
            }
            if(pollNode.right != null){
                queue.offer(pollNode.right);
                nextSum++;
            }
            if(currentSum == 0){
                currentSum = nextSum;
                nextSum = 0;
                if(!queue.isEmpty()){
                    // 若是队列不为空的话，即result就等于队列首元素的值
                    result = queue.peek().val;
                }
            }
        }
        return result;
         */

        // 方法二 ：使用两个队列，来存储当前层数的二叉树节点和下一层的二叉树节点
        // queue1,用来保存二叉树当前层的所有节点;queue2,用来保存二叉树下一层的所有节点
        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        queue1.offer(root);
        int result = root.val;
        while(!queue1.isEmpty()){
            TreeNode pollNode = queue1.poll();
            if (pollNode.left != null){
                queue2.offer(pollNode.left);
            }
            if(pollNode.right != null){
                queue2.offer(pollNode.right);
            }
            if(queue1.isEmpty()){
                queue1 = queue2;
                queue2 = new LinkedList<>();
                if(!queue1.isEmpty()){
                    result = queue1.peek().val;
                }
            }
        }
        return result;
    }


    /**
     *  总结 ：
     *  由于需要去进行二叉树的广度优先遍历，即会去遍历整个二叉树的节点；
     *  （1）时间复杂度 ： O（n）；
     *  （2）空间复杂度 ： 单队列 ：O（max{二叉树某层最大节点数}）； 双队列 ：O（max{二叉树某层两层相加的最大节点数}）
     */
}
